<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8"> <meta name="viewport" content="width=device-width">
    <title>codeforces 620</title>
    <meta name="viewport" content="width=device-width,initial-scale=1, shrink-to-fit=no">
    <!-- Bootstrap CSS -->
    <link rel="stylesheet"
          href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/css/bootstrap.min.css"
          integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk"
          crossorigin="anonymous">
    <link rel="stylesheet"
          href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/androidstudio.min.css">
<!--    <link rel="stylesheet" href="/web_template_css.css">-->
    <!-- this is highlight.js -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async
            src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.slim.min.js"
    integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js"
    integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/js/bootstrap.min.js"
    integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
    <style>
      img{
        display: block;
        height: auto;
        max-width: 100%;
      }
    </style>
  </head>
  <body>
    <nav class="navbar navbar-expand-lg navbar-light bg-light">
        <a class="navbar-brand" href="#">kvrmnks</a>
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
          <span class="navbar-toggler-icon"></span>
        </button>
        <div class="collapse navbar-collapse" id="navbarNav">
          <ul class="navbar-nav">
            <li class="nav-item active">
              <a class="nav-link" href="./../../../../../index.html" target="_self">Home <span class="sr-only">(current)</span></a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../blog.html">Blog</a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../about.html">About</a>
            </li>
          </ul>
        </div>
      </nav>



    <div class='container'>
      <p>老年人来打场div2
<!--more--></p>

<h4>A</h4>

<h5>题目简介</h5>

<p>两只兔子往中间跳,问能不能跳到一起,能输出时间</p>

<p>傻逼题</p>

<pre><code class="language-cpp">#include&lt;bits/stdc++.h&gt;
using namespace std;
int main(){
    int t;
    scanf(&quot;%d&quot;,&amp;t);
    for(int i=1;i&lt;=t;i++){
        int x,y,a,b;
        scanf(&quot;%d%d%d%d&quot;,&amp;x,&amp;y,&amp;a,&amp;b);
        y-=x;
        a+=b;
        if(y%a){
            puts(&quot;-1&quot;);
        }else{
            printf(&quot;%d\n&quot;,y/a);
        }
    } 
    
    return 0;
} 
</code></pre>

<h4>B</h4>

<h5>题目大意</h5>

<p>给一些长度一样长的字符串,问最多能构造出多长的回文串</p>

<p>傻逼题*2</p>

<pre><code class="language-cpp">#include&lt;bits/stdc++.h&gt;
using namespace std;
const int MAXN = 105;
bool isRev[MAXN];
bool used[MAXN];
bool lk[MAXN][MAXN];
char str[MAXN][55];
int n,m;
int Q[MAXN],top;
bool isR(int x){
    bool flag = true;
    for(int i=1;i&lt;=m;i++){
        if(str[x][i] != str[x][m-i+1]){
            flag = false;
        }
    }
    return flag;
}
bool canlk(int x,int y){
    bool falg = true;
    for(int i=1;i&lt;=m;i++){
        if(str[x][i] != str[y][m-i+1]){
            falg = false;
            break;
        }
    }
    return falg;
}
int main(){
    scanf(&quot;%d%d&quot;,&amp;n,&amp;m);
    for(int i=1;i&lt;=n;i++){
        scanf(&quot;%s&quot;,str[i]+1);
    }
    for(int i=1;i&lt;=n;i++)
        isRev[i] = isR(i);
    for(int i=1;i&lt;=n;i++){
        for(int j=i+1;j&lt;=n;j++){
            lk[i][j] = lk[j][i] = canlk(i,j);
        }
    }
    int mxlen = 0;
    for(int i=1;i&lt;=n;i++){
        for(int j=i+1;j&lt;=n;j++){
            if(lk[i][j] &amp;&amp; used[i]==false &amp;&amp; used[j] == false){
                mxlen += 2*m;
                used[i] = used[j] = true;
            }
        }
    }
    int tmp = 0;
    memset(used,0,sizeof used);
    for(int i=1;i&lt;=n;i++){
        memset(used,0,sizeof used);
        tmp = 0;
        if(isRev[i]){
            used[i] = true;
            tmp += m;
            for(int j=1;j&lt;=n;j++){
                for(int k=j+1;k&lt;=n;k++){
                    if(lk[j][k] &amp;&amp; used[j]==false &amp;&amp; used[k]==false){
                        tmp += m*2;
                        used[j] = used[k] = true;
                    }
                }
            }
            mxlen = max(mxlen,tmp);
        }
    }
    printf(&quot;%d\n&quot;,mxlen);
    tmp = 0;
    memset(used,0,sizeof used);
    for(int i=1;i&lt;=n;i++){
        for(int j=i+1;j&lt;=n;j++){
            if(lk[i][j] &amp;&amp; used[i]==false &amp;&amp; used[j] == false){
                tmp += 2*m;
                used[i] = used[j] = true;
            }
        }
    }
    if(tmp == mxlen){
        memset(used,0,sizeof used);
        for(int i=1;i&lt;=n;i++){
            for(int j=i+1;j&lt;=n;j++){
                if(lk[i][j] &amp;&amp; used[i]==false &amp;&amp; used[j] == false){
                    //tmp += 2*m;
                    Q[++top] = i;
                    Q[++top] = j;
                    used[i] = used[j] = true;
                }
            }
        }   
        for(int i=1;i&lt;=top;i+=2){
            printf(&quot;%s&quot;,str[Q[i]]+1);
        }
        for(int i=top;i&gt;=1;i-=2){
            printf(&quot;%s&quot;,str[Q[i]]+1);
        }
        return 0;
    }
    for(int i=1;i&lt;=n;i++){
        memset(used,0,sizeof used);
        tmp = 0;
        if(isRev[i]){
            used[i] = true;
            tmp += m;
            for(int j=1;j&lt;=n;j++){
                for(int k=j+1;k&lt;=n;k++){
                    if(lk[j][k] &amp;&amp; used[j]==false &amp;&amp; used[k]==false){
                        tmp += m*2;
                        used[j] = used[k] = true;
                    }
                }
            }
            //mxlen = max(mxlen,tmp);
        }
        if(tmp == mxlen){
            memset(used,0,sizeof used);
            Q[0] = i;
            used[i] = true;
            for(int j=1;j&lt;=n;j++){
                for(int k=j+1;k&lt;=n;k++){
                    if(lk[j][k] &amp;&amp; used[j]==false &amp;&amp; used[k]==false){
                        //tmp += m*2;
                        Q[++top] = j;
                        Q[++top] = k;
                        used[j] = used[k] = true;
                    }
                }
            }
            for(int i=1;i&lt;=top;i+=2){
                printf(&quot;%s&quot;,str[Q[i]]+1);
            }
            printf(&quot;%s&quot;,str[Q[0]]+1);
            for(int i=top;i&gt;=1;i-=2){
                printf(&quot;%s&quot;,str[Q[i]]+1);
            }   
            return 0;       
        }
    }
    return 0;
}
</code></pre>

<h4>C</h4>

<h5>题目大意</h5>

<p>在一个数轴上,给定起点,1s只能走一个单位长度,给n个区间,问能不能,在相应的时间属于相应的区间</p>

<p>数据范围差评,好久没打cf了,总是想找个1e7+的复杂度...</p>

<p>直接每步维护一个区间</p>

<p>xjb求交就行了</p>

<pre><code class="language-cpp">#include&lt;bits/stdc++.h&gt;
using namespace std;
typedef long long ll;
const int MAXN = 120;
ll t[MAXN],l[MAXN],r[MAXN];
int n;
ll L,R;
void solve(){
    scanf(&quot;%d%lld&quot;,&amp;n,&amp;L);
    R = L;
    for(int i=1;i&lt;=n;i++){
        scanf(&quot;%lld%lld%lld&quot;,&amp;t[i],&amp;l[i],&amp;r[i]);
    }
    for(int i=1;i&lt;=n;i++){
        L -= t[i] - t[i-1];
        R += t[i] - t[i-1];
        if(L&gt;r[i] || R &lt; l[i]){
            puts(&quot;NO&quot;);
            return;
        }else{
            L = max(L,l[i]);
            R = min(R,r[i]);
        }
    }
    puts(&quot;YES&quot;);
}
int main(){
    int Q;
    scanf(&quot;%d&quot;,&amp;Q);
    while(Q--){
        solve();
    }
    return 0;
} 
</code></pre>

<h4>D</h4>

<h5>题目大意</h5>

<p>给一个大于小于号的序列,构造两个数列,每个数&gt;=1,&lt;=n,要求一个LIS最大,一个LIS最小</p>

<p>heheda,比赛的时候看错题了</p>

<p>考虑求LIS的nlogn做法,实际上我们只需要在二分的那一步改成贪心,用贪心维护那个上升数列就好了</p>

<p>构造的时候我是先把数分层,然后每层构造,有些小细节见代码</p>

<pre><code class="language-cpp">#include&lt;bits/stdc++.h&gt;
using namespace std;
const int MAXN = 200050;
int Q,n;
char str[MAXN];
int type[MAXN],raw[MAXN];
vector&lt;int&gt; V[MAXN];
int Min;
void cons(int x,int pre){
    if(raw[x]!=0)return;
    
    if(x+1 &lt;= n &amp;&amp; type[x+1] == type[x] &amp;&amp; pre != x+1 &amp;&amp; str[x] == &#39;&gt;&#39;){
        cons(x+1,x);
        raw[x] = raw[x+1] + 1;
    }
    if(x-1 &gt;= 1 &amp;&amp; type[x-1] == type[x] &amp;&amp; pre != x-1 &amp;&amp; str[x-1] == &#39;&lt;&#39;){
        cons(x-1,x);
        raw[x] = raw[x-1] + 1;
    }
    raw[x] = Min + 1;
    Min ++;
}
void Cons(int x,int pre){
    if(raw[x]!=0)return;
    if(x-1 &gt;= 1 &amp;&amp; type[x-1] == type[x] &amp;&amp; pre != x-1 &amp;&amp; str[x-1] == &#39;&lt;&#39;){
        cons(x-1,x);
        raw[x] = raw[x-1] + 1;
    }   
    if(x+1 &lt;= n &amp;&amp; type[x+1] == type[x] &amp;&amp; pre != x+1 &amp;&amp; str[x] == &#39;&gt;&#39;){
        cons(x+1,x);
        raw[x] = raw[x+1] + 1;
    }

    raw[x] = Min + 1;
    Min ++;
}
void solve(){
    scanf(&quot;%d&quot;,&amp;n);
    scanf(&quot;%s&quot;,str+1);
    int lastpos = 1;
    int mx = 1;
    type[1] = 1;

    for(int i=1;i&lt;n;i++){
        if(str[i] == &#39;&gt;&#39;){
            lastpos = 1;
            type[i+1] = 1;
        }else{
            lastpos++;
            mx = max(mx,lastpos);
            type[i+1] = lastpos;
        }
    }
    for(int i=1;i&lt;=n;i++){
        V[type[i]].push_back(i);
    }
    Min = 0;
    for(int i=1;i&lt;=n;i++){
        for(int j=(int)V[i].size()-1;j&gt;=0;j--){
            cons(V[i][j],V[i][j]);
        }
    }
    for(int i=1;i&lt;=n;i++){
        printf(&quot;%d &quot;,raw[i]);
    }
    puts(&quot;&quot;);       
    
        
    
    for(int i=1;i&lt;=n;i++)
        V[i] = vector&lt;int&gt;();
    for(int i=1;i&lt;=n;i++)
        raw[i] = 0;
        
    lastpos = 1;
    mx = 1;
    type[1] = 1;
    
    for(int i=1;i&lt;n;i++){
        if(str[i] == &#39;&gt;&#39;){
            lastpos = 1;
            type[i+1] = 1;
        }else{
            ++mx;
            lastpos = mx;
            type[i+1] = lastpos;
        }
    }
    for(int i=1;i&lt;=n;i++){
        V[type[i]].push_back(i);
    }
    Min = 0;
    for(int i=1;i&lt;=n;i++){
        for(int j=0;j&lt;(int)V[i].size();j++){
            Cons(V[i][j],V[i][j]);
        }
    }
    for(int i=1;i&lt;=n;i++){
        printf(&quot;%d &quot;,raw[i]);
    }
    puts(&quot;&quot;);
    
    
    for(int i=1;i&lt;=n;i++)
        V[i] = vector&lt;int&gt;();
    for(int i=1;i&lt;=n;i++)
        raw[i] = 0;
}
int main(){
    scanf(&quot;%d&quot;,&amp;Q);
    while(Q--){
        solve();
    }
    return 0;
}
</code></pre>

<p>其实原题不需要构造的答案是个排列</p>

<p><del>我只是不会写不是排列的做法</del></p>

<h4>E</h4>

<h5>题目大意</h5>

<p>给一棵树,每次询问加一条边(x,y),询问是否有从a到b有长度等于k的可重边路径,该次询问完删掉(x,y)边</p>

<p>一共就3种可能 </p>

<p>1.a -&gt; b</p>

<p>2.a -&gt; x -&gt; y -&gt; b</p>

<p>3.a -&gt; y -&gt; x -&gt; b</p>

<p>然后只要满足小于k且奇偶性一样就行</p>

<p>好久没写树链剖分了,写得头疼...</p>

<pre><code class="language-cpp">#include&lt;bits/stdc++.h&gt;
using namespace std;
const int MAXN = 200050;
int sz[MAXN],top[MAXN],dep[MAXN],to[MAXN],nx[MAXN],h[MAXN],tot;
int ch[MAXN],fa[MAXN];
int n;
void add_edge(int x,int y){
    to[++tot] = y;
    nx[tot] = h[x];
    h[x] = tot;
}
void link(int x,int y){
    add_edge(x,y);
    add_edge(y,x);
}
void dfs1(int x,int y){
    sz[x] = 1;
    fa[x] = y;
    dep[x] = dep[y] + 1;
    for(int i=h[x];i;i=nx[i]){
        if(to[i] == y)
            continue;
        dfs1(to[i],x);
        sz[x] += sz[to[i]];
        if(sz[to[i]] &gt; sz[ch[x]])
            ch[x] = to[i];
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        dep[top[x]] &gt; dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
    }
    return dep[x]&lt;dep[y]?x:y;
}
int dis(int x,int y){
    return dep[x] + dep[y] - 2 * dep[lca(x,y)];
}
void dfs2(int x,int tp){
    top[x] = tp;
    if(ch[x])dfs2(ch[x],tp);
    for(int i=h[x];i;i=nx[i]){
        if(to[i] == fa[x] || to[i] == ch[x])
            continue;
        dfs2(to[i],to[i]);
    }
}
int main(){
    scanf(&quot;%d&quot;,&amp;n);
    for(int i=1;i&lt;n;i++){
        int x,y;
        scanf(&quot;%d%d&quot;,&amp;x,&amp;y);
        link(x,y);
    }
    dfs1(1,0);
    dfs2(1,1);
    int Q,x,y,a,b,k;
    scanf(&quot;%d&quot;,&amp;Q);
    while(Q--){
        scanf(&quot;%d%d%d%d%d&quot;,&amp;a,&amp;b,&amp;x,&amp;y,&amp;k);
    //  cout&lt;&lt;lca(x,y)&lt;&lt;endl;
        int tmp = dis(x,y);
        if(tmp &lt;= k &amp;&amp; ((k-tmp)%2==0)){puts(&quot;YES&quot;);continue;}
        tmp = dis(x,a)+dis(y,b)+1;
        if(tmp &lt;= k &amp;&amp; ((k-tmp)%2==0)){puts(&quot;YES&quot;);continue;}
        tmp = dis(x,b) + dis(y,a) + 1;
        if(tmp &lt;= k &amp;&amp; ((k-tmp)%2==0)){puts(&quot;YES&quot;);continue;}
        puts(&quot;NO&quot;);
    }
    return 0;
} 
</code></pre>

<h4>F</h4>

<h5>简单口胡</h5>

<p>老年人不想写线段树了...</p>

<p>咕咕咕</p>


    </div>
    <script>
      hljs.initHighlightingOnLoad()
    </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlightjs-line-numbers.js/2.5.0/highlightjs-line-numbers.min.js"></script>
  <script>
      hljs.initHighlightingOnLoad();
      hljs.initLineNumbersOnLoad();
  </script>
  </body>
</html>